/**
 * @file 026.重排链表.cc
 * @author snow-tyan (zziywang@163.com)
 * @brief {Life is too short to learn cpp.}
 * @version 0.1
 * @date 2021-12-10
 *
 * @copyright Copyright (c) 2021
 *
 */

#include <iostream>
#include <string>
#include <vector>
using namespace std;

struct ListNode {
    ListNode(int val = 0, ListNode *next = nullptr)
        : val(val), next(next) {}
    int val;
    ListNode *next;
};

class Solution
{
public:
    void reorderList(ListNode *head)
    {
        // 0->1->2->...->n-1->n
        // 找中点，逆序，合并链表
        // 0->1->...
        // n->n-1->...
        // 0->n->1->n-1->...

        // 找中点
        ListNode *slow = head, *fast = head;
        while (fast->next && fast->next->next) {
            fast = fast->next->next;
            slow = slow->next;
        }
        // 逆序后半段
        slow = reverseList(slow);
        // 合并新链表
        mergeList(head, slow);
    }

private:
    ListNode *reverseList(ListNode *head)
    {
        ListNode *cur = head, *pre = nullptr;
        while (cur) {
            ListNode *post = cur->next;
            cur->next = pre;
            pre = cur;
            cur = post;
        }
        return pre;
    }
    void mergeList(ListNode *l1, ListNode *l2)
    {
        while (l1 && l2) {
            ListNode *l1_post = l1->next;
            ListNode *l2_post = l2->next;

            l1->next = l2;
            l1 = l1_post;

            l2->next = l1;
            l2 = l2_post;
        }
    }
};